package arithmetic.LeetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * @author jiangfeng on 2024/1/4
 */
public class findCycle {
    public static void main(String[] args) {


        System.out.println(new Solution().canFinish(5, new int[][] {{1, 4}, {2, 4}, {3, 1}, {3, 2}}));
        //        System.out.println(new Solution().canFinish(3,new int[][]{{1,0},{1,2},{0,1}}));
        //        System.out.println(new Solution().canFinish(2,new int[][]{{1,0},{0,1}}));
        System.out.println(new Solution().canFinish(2, new int[][] {{1, 0}, {2, 0}, {0, 2}}));
        System.out.println(new Solution().canFinish(2,
                new int[][] {{1, 0}, {0, 3}, {0, 2}, {3, 2}, {2, 5}, {4, 5}, {5, 6}, {2, 4}}));
    }



    static class Solution {

        class PreCourses {
            List<Integer> courses = new ArrayList<>();
            boolean canFinish;
        }

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Map<Integer, PreCourses> map = new HashMap<>();
            for (int i = 0; i < prerequisites.length; i++) {
                PreCourses l = map.getOrDefault(prerequisites[i][0], new PreCourses());
                l.courses.add(prerequisites[i][1]);
                map.put(prerequisites[i][0], l);
            }
            Deque<Integer> dq = new ArrayDeque<>();
            for (int i = 0; i < prerequisites.length; i++) {
                if (isCycle(prerequisites[i][0], dq, map)) {
                    return false;
                }
            }
            return true;
        }

        public boolean isCycle(Integer value, Deque<Integer> dq, Map<Integer, PreCourses> map) {
            PreCourses courses = map.get(value);
            if (courses == null || courses.canFinish) {
                //   没有前置课，或者已经有前置课但已经计算过能修 快速返回.
                return false;
            }
            // 开始计算是否能修
            dq.push(value);
            for (Integer k : courses.courses) {
                //  该课已经在依赖路径里啦 有环直接否定
                if (dq.contains(k)) {
                    return true;
                }
                // 并列多个 前置条件，需要都满足
                if (isCycle(k, dq, map)) {
                    return true;
                }
            }
            // 全部满足了能修 标记一下，可以出栈
            courses.canFinish = true;
            dq.pop();
            return false;
        }
    }

    // 错误的
    static class Solution2 {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            if (prerequisites.length == 0) {
                return true;
            }
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < prerequisites.length; i++) {
                map.put(prerequisites[i][0], prerequisites[i][0]);
            }

            // 需要预备的 放进来。
            Set<Integer> preSet = new HashSet<>();
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < prerequisites.length; i++) {
                stack.push(prerequisites[i][0]);
                preSet.add(prerequisites[i][0]);
                if (map.containsKey(prerequisites[i][1])) {
                    if (preSet.contains(prerequisites[i][1])) {
                        // 直接清栈 卡死了，里面都是无效元素
                        return false;
                    } else {
                        stack.push(prerequisites[i][1]);
                        preSet.add(prerequisites[i][0]);
                    }
                } else {
                    // 可以清除栈了
                    while (!stack.empty()) {
                        preSet.remove(stack.pop());
                    }

                }
            }
            return true;

        }
    }

}
